//给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则： 
//
// 
// 任何左括号 ( 必须有相应的右括号 )。 
// 任何右括号 ) 必须有相应的左括号 ( 。 
// 左括号 ( 必须在对应的右括号之前 )。 
// * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。 
// 一个空字符串也被视为有效字符串。 
// 
//
// 示例 1: 
//
// 
//输入: "()"
//输出: True
// 
//
// 示例 2: 
//
// 
//输入: "(*)"
//输出: True
// 
//
// 示例 3: 
//
// 
//输入: "(*))"
//输出: True
// 
//
// 注意: 
//
// 
// 字符串大小将在 [1，100] 范围内。 
// 
// Related Topics 栈 贪心 字符串 动态规划 
// 👍 399 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func checkValidString(s string) bool {
    // 解法1：
    // 使用两个栈 分别存储* 和 左括号， 碰到右括号的时候先check左括号再处理 *
    // 到最后如果左括号栈不为空， 则弹出左括号值 再弹出*（需要判断* 和 左括号次序） 失败则否
    // 因为最后不知道* 和 左括号的次序，所以入栈的数据为s的索引

    // 解法2:
    // 贪心算法

    minCount, maxCount := 0, 0 // 标识左括号的最小值和最大值

    for i := range s {
        switch s[i] {
            case '(' :
                minCount++
                maxCount++
                break

            case ')':
                minCount = max(minCount-1, 0)
                maxCount--

                if maxCount < 0 {  // 如果最大值小鱼0  代表无论怎样都不合法
                    return false
                }
                break

            case '*':
                minCount = max(minCount-1, 0)
                maxCount++
        }
    }

    return minCount == 0
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
//leetcode submit region end(Prohibit modification and deletion)
